package code;

import java.util.ArrayList;
import java.util.List;

//太平洋大西洋水流问题：https://leetcode.cn/problems/pacific-atlantic-water-flow/
//时间复杂度： O(M*N)
public class Test1 {
	int m,n;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] grid1,grid2;
    List<List<Integer>> ret;
    //给定一个位置[i,j]经可能的往外扩散
    public void dfs(int[][] heights,int i,int j,boolean[][] grid){
        grid[i][j]=true;
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&y>=0&&x<m&&y<n&&grid[x][y]==false&&heights[x][y]>=heights[i][j]){
                dfs(heights,x,y,grid);
            }
        }
    }
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m=heights.length;
        n=heights[0].length;
        grid1=new boolean[m][n];
        grid2=new boolean[m][n];
        ret=new ArrayList<>();

        //处理太平洋
        for(int k=0;k<n;k++){
            dfs(heights,0,k,grid1);
        }
        for(int k=0;k<m;k++){
            dfs(heights,k,0,grid1);
        }
        
        //处理大西洋
        for(int k=0;k<n;k++){
            dfs(heights,m-1,k,grid2);
        }
        for(int k=0;k<m;k++){
            dfs(heights,k,n-1,grid2);
        }

        //收集结果
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid1[i][j]&&grid2[i][j]){
                    ret.add(Arrays.asList(i, j));
                }
            }
        }
        return ret;
    }	
}
